/*************************************************************************
	> File Name: 004.binary_search.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  9/27 19:40:20 2021
 ************************************************************************/

#include <stdio.h>

#define P(func) {\
    printf("%s = %d\n", #func, func);\
}

/*
 * 最基本的二分查找
 */
int binary_search_v1(int *arr, int n, int x) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid;
        if (arr[mid] < x) head = mid + 1;
        else tail = mid - 1;
    }
    return -1;
}


/*
 * 特殊情况1: 1111100000(找到最后一个1出现的位置)
 */
int binary_search_v2(int *arr, int n) {
    int head = -1; //小技巧：head指向虚拟头指针
    int tail = n - 1;
    int mid;
    while (head < tail) {
        mid = (head + tail + 1) >> 1; //!!!特别注意
        if (arr[mid] == 1) head = mid;
        else tail = mid - 1;
    }
    return head;
}

/*
 * 特殊情况2：0000011111（找到第一个1出现的位置）
 */
int binary_search_v3(int *arr, int n) {
    int head = 0;
    int tail = n; 
    int mid;
    while (head < tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == 1) tail = mid;
        else head = mid + 1;
    }
    return head == n ? -1 : head;
}

int main() {
    int arr1[10] = {1, 3, 5, 7, 9, 11, 13, 17, 19, 21};
    int arr2[10] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
    int arr3[10] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
    P(binary_search_v1(arr1, 10, 7));
    P(binary_search_v2(arr2, 10));
    P(binary_search_v3(arr3, 10));
    return 0;
}
